﻿#define _CRT_SECURE_NO_WARNINGS 1
//计算右侧⼩于当前元素的个数（hard):https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
class Solution
{
	vector<int> ret;
	vector<int> index; // 记录 nums 中当前元素的原始下标
	int tmpNums[500010];
	int tmpIndex[500010];
public:
	vector<int> countSmaller(vector<int>& nums)
	{
		int n = nums.size();
		ret.resize(n);
		index.resize(n);
		// 初始化⼀下 index 数组
		for (int i = 0; i < n; i++)
			index[i] = i;
		mergeSort(nums, 0, n - 1);
		return ret;
	}

	void mergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return;
		// 1. 根据中间元素，划分区间
		int mid = (left + right) >> 1;
		// [left, mid] [mid + 1, right]
		// 2. 先处理左右两部分
		mergeSort(nums, left, mid);
		mergeSort(nums, mid + 1, right);
		// 3. 处理⼀左⼀右的情况
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right) // 降序
		{
			if (nums[cur1] <= nums[cur2])
			{
				tmpNums[i] = nums[cur2];
				tmpIndex[i++] = index[cur2++];
			}
			else
			{
				ret[index[cur1]] += right - cur2 + 1; // 重点
				tmpNums[i] = nums[cur1];
				tmpIndex[i++] = index[cur1++];
			}
		}
		// 4. 处理剩下的排序过程
		while (cur1 <= mid)
		{
			tmpNums[i] = nums[cur1];
			tmpIndex[i++] = index[cur1++];
		}
		while (cur2 <= right)
		{
			tmpNums[i] = nums[cur2];
			tmpIndex[i++] = index[cur2++];
		}
		for (int j = left; j <= right; j++)
		{
			nums[j] = tmpNums[j - left];
			index[j] = tmpIndex[j - left];
		}
	}
};